#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

int n;
vector<vector<int>> distance;
int minLength = INT_MAX;

void tsp(vector<int>& path, vector<bool>& visited, int curLength, int curNode) {
    if (find(visited.begin(), visited.end(), false) == visited.end()) {
        curLength += distance[curNode][path[0]];
        minLength = min(minLength, curLength);
        return;
    }

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            visited[i] = true;
            path.push_back(i);
            curLength += distance[curNode][i];

            if (curLength < minLength) {
                tsp(path, visited, curLength, i);
            }

            visited[i] = false;
            path.pop_back();
            curLength -= distance[curNode][i];
        }
    }
}

int main() {
    cout << "Enter number of cities: ";
    cin >> n;
    
    distance.resize(n, vector<int>(n, 0));
    cout << "Enter distance matrix: " << endl;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> distance[i][j];
        }
    }

    vector<int> path;
    vector<bool> visited(n, false);

    path.push_back(0);
    visited[0] = true;

    tsp(path, visited, 0, 0);

    cout << "Minimum distance: " << minLength << endl;

    return 0;
}